/**
 *  Copyright (C) 2010 Travis Brown
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package org.scalaq.q.implicit;

import java.io.*;
import java.util.*;

public class J01 {
  private static double[] readFile(File file) throws IOException {
    List<Double> coordinates = new ArrayList<Double>();

    BufferedReader reader = new BufferedReader(new FileReader(file));
    String line = reader.readLine();
    while (line != null) {
      String[] fields = line.split("\t");
      coordinates.add(Double.parseDouble(fields[0]) * Math.PI / 180.0);
      coordinates.add(Double.parseDouble(fields[1]) * Math.PI / 180.0);
      line = reader.readLine();
    }

    double[] pcoordinates = new double[coordinates.size()];

    for (int i = 0; i < coordinates.size(); i++) {
      pcoordinates[i] = coordinates.get(i);
    }

    return pcoordinates;
  }

  private static double distance(double latA, double lngA, double latB, double lngB) {
    return Math.acos(Math.sin(latA) * Math.sin(latB)
         + Math.cos(latA) * Math.cos(latB) * Math.cos(lngB - lngA));
  }

  private static int nearest(double[] centers, double lat, double lng) {
    int k = centers.length / 2;
    int minI = -1;
    double minV = Double.POSITIVE_INFINITY;

    for (int i = 0; i < k; i++) {
      double v = J01.distance(lat, lng, centers[i * 2], centers[i * 2 + 1]);
      if (v < minV) {
        minV = v;
        minI = i;
      }
    }

    return minI;
  }

  /**
   * Compute the approximate centroid by taking the average of the latitudes
   * and longitudes.
   */
  private static double[] centroid(List<Double> coordinates) {
    int n = coordinates.size();

    double latSins = 0.0;
    double latCoss = 0.0;
    double lngSins = 0.0;
    double lngCoss = 0.0;

    for (int i = 0; i < n; i += 2) {
      latSins += Math.sin(coordinates.get(i));
      latCoss += Math.cos(coordinates.get(i));
      lngSins += Math.sin(coordinates.get(i + 1));
      lngCoss += Math.cos(coordinates.get(i + 1));
    }

    latSins /= n;
    latCoss /= n;
    lngSins /= n;
    lngCoss /= n;

    double lat = Math.atan2(latSins, latCoss);
    double lng = Math.atan2(lngSins, lngCoss);

    return new double[] { lat, lng };
  }

  private static double[] init(double[] coordinates, int k, Random rand) {
    int n = coordinates.length / 2;
    double[] centers = new double[k * 2];

    for (int i = 0; i < k; i++) {
      int j = rand.nextInt(n);

      centers[i * 2] = coordinates[j * 2];
      centers[i * 2 + 1] = coordinates[j * 2 + 1];
    }

    return centers;
  }

  private static int[] assign(double[] coordinates, double[] centers) {
    int n = coordinates.length / 2;
    int[] assignments = new int[n];

    for (int i = 0; i < n; i++) {
      assignments[i] = J01.nearest(centers, coordinates[i * 2], coordinates[i * 2 + 1]);
    }

    return assignments;
  }

  private static double[] clusters(double[] coordinates, int k, Random rand) {
    int n = coordinates.length / 2;
    double[] centers = J01.init(coordinates, k, rand);

    int[] assignments = J01.assign(coordinates, centers);
    boolean done = false;

    List<List<Double>> clusters = new ArrayList<List<Double>>(k);
    for (int i = 0; i < k; i++) {
      clusters.add(new ArrayList<Double>());
    }

    while (!done) {
      for (int i = 0; i < k; i++) {
        clusters.get(i).clear();
      }

      for (int i = 0; i < n; i++) {
        clusters.get(assignments[i]).add(coordinates[i * 2]);
        clusters.get(assignments[i]).add(coordinates[i * 2 + 1]);
      }

      for (int i = 0; i < k; i++) {
        double[] centroid = J01.centroid(clusters.get(i));
        centers[i * 2] = centroid[0];
        centers[i * 2 + 1] = centroid[1];
      }

      int[] assignmentsNew = J01.assign(coordinates, centers);
      done = true;
      for (int i = 0; i < n; i++) {
        if (assignmentsNew[i] != assignments[i]) {
          done = false;
          break;
        }
      }
      assignments = assignmentsNew;
    }

    return centers;   
  }

  public static void main(String[] args) throws IOException {
    String filename = args[0];
    int k = Integer.parseInt(args[1]);

    Random rand = new Random(1001);

    double[] coordinates = J01.readFile(new File(filename));
    double[] centers = J01.clusters(coordinates, k, rand);
    for (int i = 0; i < k; i++) {
      double lat = centers[i * 2] * 180.0 / Math.PI;
      double lng = centers[i * 2 + 1] * 180.0 / Math.PI;
      System.out.println(lat + " " + lng);
    }
  }
}

